#include "fs/fs.h"
#include "fs/buf.h"
#include "fs/inode.h"
#include "fs/dir.h"
#include "fs/bitmap.h"
#include "lib/str.h"
#include "lib/print.h"
#include "proc/cpu.h"
#include "mem/vmem.h"

// 对目录文件的简化性假设: 每个目录文件只包括一个block
// 也就是每个目录下最多 BLOCK_SIZE / sizeof(dirent_t) = 32 个目录项

// 查询一个目录项是否在目录里
// 成功返回这个目录项的inode_num
// 失败返回INODE_NUM_UNUSED
// ps: 调用者需持有pip的锁
uint16 dir_search_entry(inode_t *pip, char *name)
{
    assert(sleeplock_holding(&pip->slk), "dir_search_entry: lock");
    
    buf_t* buf = buf_read(pip->addrs[0]);  // 读取目录块
    for (uint32 offset = 0; offset < BLOCK_SIZE; offset += sizeof(dirent_t)) 
    {
        dirent_t* de = (dirent_t*)(buf->data + offset);
        if (de->name[0] == 0) continue;  // 空目录项跳过
        if (strncmp(de->name, name, DIR_NAME_LEN) == 0) {
            uint16 inode_num = de->inode_num;
            buf_release(buf);  // 找到后立即释放缓冲区
            return inode_num;
        }
    }
    buf_release(buf);  // 遍历结束后释放缓冲区
    return INODE_NUM_UNUSED;  // 未找到返回INODE_NUM_UNUSED
}

// 在pip目录下添加一个目录项
// 成功返回这个目录项的偏移量 (同时更新pip->size)
// 失败返回BLOCK_SIZE (没有空间 或 发生重名)
// ps: 调用者需持有pip的锁
uint32 dir_add_entry(inode_t *pip, uint16 inode_num, char *name)
{
    // assert(sleeplock_holding(&pip->slk), "dir_add_entry: lock");

    // // 确保第一个数据块已分配
    // if (pip->addrs[0] == 0) {
    //     uint32 block_num = bitmap_alloc_block();
    //     assert(block_num != 0, "dir_add_entry: failed to allocate block");
    //     pip->addrs[0] = block_num;  // 将分配的新块写入addrs[0]
    //     pip->size = 0;  // 初始化目录大小
    //     inode_rw(pip, true);  // 将更新写回磁盘
    // }

    // // 读取第一个数据块
    // buf_t* buf = buf_read(pip->addrs[0]);

    // // 遍历目录项
    // bool flag = false;
    // uint32 ans = BLOCK_SIZE;

    // for (uint32 offset = 0; offset < BLOCK_SIZE; offset += sizeof(dirent_t)) {
    //     dirent_t* de = (dirent_t*)(buf->data + offset);

    //     // 空目录项
    //     if (de->name[0] == 0) {
    //         if (!flag) {
    //             flag = true;
    //             de->inode_num = inode_num;          // 写入inode号
    //             memmove(de->name, name, DIR_NAME_LEN);  // 写入目录名
    //             ans = offset;                      // 返回偏移量
    //             pip->size += sizeof(dirent_t);     // 更新目录大小
    //             inode_rw(pip, true);               // 写回inode的元数据
    //         }
    //     }
    //     // 检测重名
    //     else if (strncmp(de->name, name, DIR_NAME_LEN) == 0) {
    //         printf("dir_add_entry：重名");
    //         ans = BLOCK_SIZE;  // 重名，返回错误
    //         break;
    //     }
    // }

    // buf_write(buf);    // 写回数据块
    // buf_release(buf);  // 释放buf
    // return ans;
     int off;
    struct dirent de;

    // 发生重名
    uint16 num = dir_search_entry(pip, name);
    if (num != INODE_NUM_UNUSED)
        return BLOCK_SIZE;

    // 寻找空的目录项
    for (off = 0; off < pip->size; off += sizeof(de))
    {
        if (inode_read_data(pip, off, sizeof(de), &de, 0) != sizeof(de))
            panic("dir_add_entry: read");
        if(de.inode_num == INODE_NUM_UNUSED)
            break;
    }
    // 添加新条目
    memmove(de.name, name, DIR_NAME_LEN);
    de.inode_num = inode_num;
    if (inode_write_data(pip, off, sizeof(de), &de, 0) != sizeof(de))
        panic("dir_add_entry: write");
    return off;

}

// 在pip目录下删除一个目录项
// 成功返回这个目录项的inode_num
// 失败返回INODE_NUM_UNUSED
// ps: 调用者需持有pip的锁
uint16 dir_delete_entry(inode_t *pip, char *name)
{   assert(sleeplock_holding(&pip->slk), "dir_delete_entry: lock");

    buf_t* buf = buf_read(pip->addrs[0]);  // 读取目录块
    for (uint32 offset = 0; offset < BLOCK_SIZE; offset += sizeof(dirent_t)) {
        dirent_t* de = (dirent_t*)(buf->data + offset);
        if (de->inode_num == 0) continue;  // 空目录项跳过
        if (strncmp(de->name, name, DIR_NAME_LEN) == 0) {
            uint16 inode_num = de->inode_num;
            de->name[0] = 0;  // 清空目录名，表示删除
            pip->size -= sizeof(dirent_t);  // 更新目录大小
            buf_write(buf);  // 写回更新的数据块

            if (pip->size == 0) {
                // 如果目录项为空，释放数据块
                bitmap_free_block(pip->addrs[0]);
                pip->addrs[0] = 0;
                inode_rw(pip, true);  // 同步到磁盘
            }

            buf_release(buf);  // 释放缓冲区
            return inode_num;  // 返回被删除的inode_num
        }
    }
    buf_release(buf);  // 未找到时释放缓冲区
    return INODE_NUM_UNUSED;  // 返回失败
}

// 把目录下的有效目录项复制到dst (dst区域长度为len)
// 返回读到的字节数 (sizeof(dirent_t)*n)
// 调用者需要持有pip的锁
uint32 dir_get_entries(inode_t* pip, uint32 len, void* dst, bool user)
{
    assert(sleeplock_holding(&pip->slk), "dir_get_entries: lock");

    uint32 n = 0;  // 已拷贝的字节数
    buf_t* buf = buf_read(pip->addrs[0]);
    dirent_t* de;
    proc_t* p = myproc();
    pgtbl_t user_pgtbl = p->pgtbl;
        
    for (uint32 offset = 0; offset < BLOCK_SIZE && n + sizeof(dirent_t) <= len; offset += sizeof(dirent_t))
    {
        de = (dirent_t*)(buf->data + offset);
        if (de->name[0] == 0)  // 跳过空目录项
            continue;

        if (user)
            uvm_copyout(user_pgtbl, (uint64)((char*)dst + n), (uint64)de, sizeof(dirent_t));
        else
            memmove((char*)dst + n, de, sizeof(dirent_t));

        n += sizeof(dirent_t);  // 更新已拷贝字节数
    }

    buf_release(buf);
    return n;
}

// 改变进程里存储的当前目录
// 成功返回0 失败返回-1
uint32 dir_change(char* path)
{
    inode_t* new_dir = path_to_inode(path);

    if (new_dir == NULL) {
        printf("dir_change: path not found\n");
        return -1;
    }

    inode_lock(new_dir);
    if (new_dir->type != FT_DIR) {
        inode_unlock_free(new_dir);
        printf("dir_change: not a directory\n");
        return -1;
    }

    // 更新当前进程的当前目录
    proc_t* p = myproc();
    inode_unlock_free(p->cwd);  // 释放旧的当前目录
    p->cwd = new_dir;           // 设置新的当前目录

    return 0;
}

// 输出一个目录下的所有有效目录项
// for debug
// ps: 调用者需持有pip的锁
void dir_print(inode_t *pip)
{
    assert(sleeplock_holding(&pip->slk), "dir_print: lock");

    printf("\ninode_num = %d dirents:\n", pip->inode_num);

    dirent_t *de;
    buf_t *buf = buf_read(pip->addrs[0]);
    for (uint32 offset = 0; offset < BLOCK_SIZE; offset += sizeof(dirent_t))
    {
        de = (dirent_t *)(buf->data + offset);
        if (de->name[0] != 0)
            printf("inum = %d dirent = %s\n", de->inode_num, de->name);
    }
    buf_release(buf);
}

/*----------------------- 路径(一串目录和文件) -------------------------*/

// Examples:
//   skipelem("a/bb/c", name) = "bb/c", setting name = "a"
//   skipelem("///a//bb", name) = "bb", setting name = "a"
//   skipelem("a", name) = "", setting name = "a"
//   skipelem("", name) = skipelem("////", name) = 0


static char *skip_element(char *path, char *name)
{
    while(*path == '/') path++;
    if(*path == 0) return 0;

    char *s = path;
    while (*path != '/' && *path != 0)
        path++;

    int len = path - s;
    if (len >= DIR_NAME_LEN) {
        memmove(name, s, DIR_NAME_LEN);
    } else {
        memmove(name, s, len);
        name[len] = 0;
    }
    while (*path == '/')
        path++;
    return path;
}

// 查找路径path对应的inode (find_parent = false)
// 查找路径path对应的inode的父节点 (find_parent = true)
// 供两个上层函数使用
// 失败返回NULL
static inode_t* search_inode(char* path, char* name, bool find_parent)
{
    inode_t *ip;
    if (*path == '/')
        ip = inode_alloc(INODE_ROOT);
    else
        ip = inode_dup(myproc()->cwd);
    inode_t *next;
    while ((path = skip_element(path, name)) != 0)
    {
        inode_lock(ip);
        // 不是目录
        if (ip->type != FT_DIR)
        {
            inode_unlock_free(ip);
            return NULL;
        }
        // 找到父节点
        if (find_parent && *path == '\0')
        {
            inode_unlock(ip);
            return ip;
        }
        uint16 inum = dir_search_entry(ip, name);
        if (inum == INODE_NUM_UNUSED)
        {
            inode_unlock_free(ip);
            return NULL;
        }
        next = inode_alloc(inum);
        inode_unlock_free(ip);
        ip = next;
    }
    if (find_parent)
    {
        inode_free(ip);
        return 0;
    }
    return ip;

}

// 找到path对应的inode
inode_t* path_to_inode(char* path)
{
    char name[DIR_NAME_LEN];
    return search_inode(path, name, false);
}

// 找到path对应的inode的父节点
// path最后的目录名放入name指向的空间
inode_t* path_to_pinode(char* path, char* name)
{
    return search_inode(path, name, true);
}

// 如果path对应的inode存在则返回inode
// 如果path对应的inode不存在则创建inode
// 失败返回NULL
inode_t* path_create_inode(char* path, uint16 type, uint16 major, uint16 minor)
{
    inode_t *dp, *ip;
    ip = NULL;
    char name[DIR_NAME_LEN];
    dp = path_to_pinode(path, name);
    if (dp == 0)
        return 0;
    inode_lock(dp);
    uint16 inum = dir_search_entry(dp, name);
    if (inum != INODE_NUM_UNUSED)
        ip = inode_alloc(inum);
    else
    {
        ip = inode_create(type, major, minor);
        if (type == FT_DIR)
        {
            dp->nlink++;
            inode_rw(dp, true);
            inode_lock(ip);
            if (dir_add_entry(ip, ip->inode_num, ".") >= BLOCK_SIZE||dir_add_entry(ip, ip->inode_num, "..") >= BLOCK_SIZE)
                panic("path_create_inode: dir_add_entry fail");
            inode_unlock(ip);
        }
        if (dir_add_entry(dp, ip->inode_num, name) >= BLOCK_SIZE)
            panic("path_create_inode: dir_add_entry fail");
    }
    inode_unlock_free(dp);
    return ip;

}

// 文件链接(目录不能被链接)
// 本质是创建一个目录项, 这个目录项的inode_num是存在的而不用申请
// 成功返回0 失败返回-1
uint32 path_link(char* old_path, char* new_path)
{
    char name[DIR_NAME_LEN];
    inode_t* old_ip = path_to_inode(old_path);  // 找到old_path对应的inode
    if (old_ip == NULL) {
        printf("path_link: %s does not exist\n", old_path);
        return -1;  // 原路径不存在
    }

    inode_lock(old_ip);
    if (old_ip->type == FT_DIR) {
        inode_unlock_free(old_ip);
        printf("path_link: cannot link a directory\n");
        return -1;  // 不能链接目录
    }

    // 解析新路径的父目录
    inode_t* new_parent = path_to_pinode(new_path, name);
    if (new_parent == NULL) {
        inode_unlock_free(old_ip);
        printf("path_link: parent directory of %s not found\n", new_path);
        return -1;  // 新路径的父目录不存在
    }

    inode_lock(new_parent);
    if (new_parent->type != FT_DIR) {
        inode_unlock_free(new_parent);
        inode_unlock_free(old_ip);
        printf("path_link: parent is not a directory\n");
        return -1;  // 父目录无效
    }

    // 检查重名
    if (dir_search_entry(new_parent, name) != INODE_NUM_UNUSED) {
        inode_unlock_free(new_parent);
        inode_unlock_free(old_ip);
        printf("path_link: %s already exists\n", new_path);
        return -1;  // 目标文件名已存在
    }

    // 在父目录中添加新目录项
    if (dir_add_entry(new_parent, old_ip->inode_num, name) == BLOCK_SIZE) {
        inode_unlock_free(new_parent);
        inode_unlock_free(old_ip);
        printf("path_link: failed to add directory entry\n");
        return -1;  // 添加目录项失败
    }

    // 更新链接数并写回磁盘
    old_ip->nlink++;
    inode_rw(old_ip, true);

    inode_unlock(new_parent);
    inode_unlock_free(old_ip);

    return 0;  // 成功
}

// 检查一个unlink操作是否合理
// 调用者需要持有ip的锁
// 在path_unlink()中调用
static bool check_unlink(inode_t* ip)
{
    assert(sleeplock_holding(&ip->slk), "check_unlink: slk");

    uint8 tmp[sizeof(dirent_t) * 3];
    uint32 read_len;
    
    read_len = dir_get_entries(ip, sizeof(dirent_t) * 3, tmp, false);
    
    if(read_len == sizeof(dirent_t) * 3) {
        return false;
    } else if(read_len == sizeof(dirent_t) * 2) {
        return true;
    } else {
        panic("check_unlink: read_len");
        return false;
    }
}

// 文件删除链接
uint32 path_unlink(char* path)
{
    char name[DIR_NAME_LEN];
    inode_t* parent = path_to_pinode(path, name);  // 找到父目录的inode
    if (parent == NULL) {
        printf("path_unlink: parent directory not found\n");
        return -1;  // 父目录不存在
    }

    inode_lock(parent);
    if (parent->type != FT_DIR) {
        inode_unlock_free(parent);
        printf("path_unlink: parent is not a directory\n");
        return -1;  // 父目录无效
    }

    // 查找目标文件的inode号
    uint16 inode_num = dir_search_entry(parent, name);
    if (inode_num == INODE_NUM_UNUSED) {
        inode_unlock_free(parent);
        printf("path_unlink: %s not found\n", path);
        return -1;  // 目标文件不存在
    }

    // 获取目标文件的inode
    inode_t* ip = inode_alloc(inode_num);
    inode_lock(ip);

    if (ip->type == FT_DIR) {
        // 检查目录是否为空 (只能包含"."和"..")
        if (!check_unlink(ip)) {
            inode_unlock_free(ip);
            inode_unlock_free(parent);
            printf("path_unlink: directory not empty\n");
            return -1;  // 目录不为空，不能删除
        }
    }

    // 从父目录中删除目录项
    if (dir_delete_entry(parent, name) == INODE_NUM_UNUSED) {
        inode_unlock_free(ip);
        inode_unlock_free(parent);
        printf("path_unlink: failed to delete directory entry\n");
        return -1;  // 删除失败
    }

    // 减少链接数
    ip->nlink--;
    inode_rw(ip, true);

    // 如果链接数为0，释放文件占用的磁盘空间
    if (ip->nlink == 0) {
        inode_free_data(ip);
        inode_free(ip);
    }

    inode_unlock_free(ip);
    inode_unlock_free(parent);

    return 0;  // 成功
}